package com.zzg.algorithm.dynamic;

import java.util.Arrays;

/**
 * @Author zhengzg
 * @Date 2022-10-08
 * @Version v1.0
 * 动态规划算法：01背包问题
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        // 物品的重量
        int[] w = {1,4,3};
        // 物品的价值
        int[] val = {1500,3000,2000};
        // 背包容量
        int m = 4;
        // 物品的个数
        int n = val.length;
        // 创建二维数组
        // v[i][j] 表示在前i个物品中能够装入容量为j的背包的最大价值
        // i 为物品 ，j为重量，值为价值
        // +1对应图中的第一列第一行，本程序无实际意义
        int[][] v = new int[n+1][m+1];
        int[][] path = new int[n+1][m+1];

        for (int i = 0; i < v.length; i++) {
            // 初始化第一列
            v[i][0] = 0;
        }
        // 初始化第一行
        Arrays.fill(v[0], 0);

        // 根据前面得到的公式来动态规划处理
        for (int i = 1; i < v.length; i++) {
            // 不处理第一行，第一列，从1开始
            for (int j = 1; j < v[0].length; j++) {
                // 当前物品的重量如果大于背包重量，本行物品价值 = 上一行同列物品的价值
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    /*
                     * 如果前一行同列物品的价值 < 本行同列物品的价值 + （前一行列为 ：背包总容量 - 本行物品的重量的列的物品的价值）
                     * 将后一部分赋值给本行同列，同时记录最大价值
                     * 如果上一公式取反，则直接赋值前一行同列的值
                     */
                    if (v[i-1][j] < val[i-1] + v[i-1][j-w[i-1]]) {
                        v[i][j] = val[i-1] + v[i-1][j-w[i-1]];
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }

        // 行的最大下标
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.printf("第%d个商品放入背包\n",i);
                // j = 总容量 - 当前物品的重量 得到另外物品的重量
                j -= w[i-1];
            }
            i--;
        }
    }
}
